package zuo;

import java.util.HashMap;
import java.util.Map;

public class Leetcode {


    /**
     * 投票法
     * 时间复杂度：O（n）
     * 空间复杂度：O（1）
     * @param nums
     * @return
     */
    private Map<Integer,Integer> countNums(int[] nums){
        Map<Integer,Integer> counts=new HashMap<Integer,Integer>();
        for(int num:nums){
            if(!counts.containsKey(num)){
                counts.put(num,1);
            }else{
                counts.put(num,counts.get(num)+1);
            }
        }
        return counts;
    }
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> counts=countNums(nums);
        Map.Entry<Integer,Integer> majorityEntry=null;
        for(Map.Entry<Integer,Integer> entry:counts.entrySet()){
            if(majorityEntry==null||entry.getValue()>majorityEntry.getValue()){
                majorityEntry=entry;
            }
        }
        return majorityEntry.getKey();
    }
}
